package Alibaba;

import common.TreeNode;

import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-01-18 15:41
 * 297. 二叉树的序列化与反序列化
 * 1、前序遍历
 * 2、后序遍历
 * 3、层序遍历
 */
public class Codec297 {

    StringBuffer sb;
    // Encodes a tree to a single string.序列化
    public String serialize(TreeNode root) {
        sb=new StringBuffer();
        preOrder(root);
        return sb.toString();
    }
    void preOrder(TreeNode root){
        if (root==null){
            sb.append("#").append(',');
            return;
        }
        sb.append(root.val).append(",");
        preOrder(root.left);
        preOrder(root.right);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] datas = data.split(",");
        LinkedList<String> nodes=new LinkedList<>();
        for (int i = 0; i < datas.length; i++) {
            nodes.add(datas[i]);
        }
        return build(nodes);
    }
    TreeNode build(LinkedList<String> nodes){
        if (nodes.isEmpty()){
            return null;
        }
        String first = nodes.removeFirst();
        if (first.equals("#")){
            return null;
        }
        int rootval=Integer.parseInt(first);
        TreeNode root=new TreeNode(rootval);
        root.left=build(nodes);
        root.right=build(nodes);
        return root;
    }
}
